package day_2022_9_to_12.Day;

import java.util.HashSet;
import java.util.Set;

/**
 * @author haomin
 * @date 2022/10/17 10:05
 **/
public class Day45_1_Num904_TotalFruit {
    // 原地窗口 超时
    class Solution {
        public int totalFruit(int[] fruits) {
            int max = 0;
            int[] arr = new int[fruits.length];
            for(int i = 0; i < fruits.length; ++i){
                Set<Integer> set = new HashSet<>();
                int j = i;
                while(j < fruits.length && set.size() < 3) {
                    set.add(fruits[j]);
                    j++;
                }
                arr[i] = j-i-1;
                if(j == fruits.length && set.size() < 3) arr[i] += 1;
                max = Math.max(max, arr[i]);
            }
            return max;
        }
    }
    // 滑动窗口 动态
    class Solution2 {
        public int totalFruit(int[] fruits) {
            int max = 0;
            int n = fruits.length;
            int[] count = new int[n+1];
            for(int i = 0, j = 0, size = 0; i < n; ++i){
                while(j < n && size <= 2){
                    count[fruits[j]]++;
                    if(count[fruits[j]] == 1) size++;
                    j++;
                }
                max = Math.max(max, size <= 2 ? j-i : j-i-1);
                count[fruits[i]]--;
                if(count[fruits[i]] == 0) size--;
            }
            return max;
        }
    }
}